package Exams.Unity;

import java.util.*;
import java.math.*;

public class q1 {
    private static final long MOD_VALUE = 1000000007L;
    private static final int THRESHOLD = 10;

    /*
    填充数组，应该用dp做
    https://www.nowcoder.com/questionTerminal/3e34d9ed0bbc4db68b6fbca20a62926d?orderByHotValue=1&mutiTagIds=578&page=1
     */
    public int FillArray(int[] a, int k) {
        // write code here
        int start = 1, end = k;
        int count = 0;
        BigInteger result = BigInteger.ONE;

        int[] a1 = new int[a.length + 2];
        a1[0] = 1;
        a1[a.length + 1] = k;
        System.arraycopy(a, 0, a1, 1, a.length);

        for (int i = 0; i < a1.length; i++) {
            if (a1[i] != 0) {
                if (count == 0) {
                    start = Math.max(1, a1[i]);
                } else {
                    end = Math.min(a1[i], k);
                    result = result.multiply(BigInteger.valueOf(partialFillArray(start, count, end)));
                    count = 0;
                    start = end;
                }
            } else {
                count++;
            }
        }

        return mod(result);
    }

    // [start, 0, ... , 0, end]
    public int partialFillArray(int start, int count, int end) {
//        System.out.printf("[%d, 0 * %d, %d]\n", start, count, end);
        int n = end - start + 1;
        if (count < THRESHOLD || n < THRESHOLD) {
            return partialFillArray(n, count);
        } else {
            return bigIntegerPartialFillArray(n, count);
        }
    }

    private int partialFillArray(int n, int count) {
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = 1;
        }

        for (int i = 1; i < count; i++) {
            for (int j = n - 2; j >= 0; j--) {
                array[j] = array[j] + array[j + 1];
            }
        }

        return Arrays.stream(array).sum();
    }

    private int bigIntegerPartialFillArray(int n, int count) {
        BigInteger[] array = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            array[i] = BigInteger.ONE;
        }

        for (int i = 1; i < count; i++) {
            for (int j = n - 2; j >= 0; j--) {
                array[j] = array[j].add(array[j + 1]);
            }
        }

        BigInteger sum = Arrays.stream(array).reduce(BigInteger.ZERO, (x, y) -> x = x.add(y));
        return mod(sum);
    }

    private int mod(BigInteger result) {
        return result.remainder(BigInteger.valueOf(MOD_VALUE)).intValue();
    }

}
